package com.ctrip.study.algorithm.pratice;

import org.junit.Test;

import junit.framework.TestCase;

/**
 * 输入一个单向链表，输出该链表中倒数第k个结点。
 * 链表的倒数第0个结点为链表的尾指针.
 */
public class LinkReciprocal extends TestCase{
	
	@Test
	public void test(){
		Link link = getLink();
		System.out.println(link);
		Node node = getReciprocal(link, 3);
		System.out.println(node);
	}

	
	private Node getReciprocal(Link link, int index) {
		Node head = link.head;
		Node pre = head;
		for (int i = 0; i < index; i++) {
			pre = pre.next;
		}
		Node next = head;
		while(pre != null){
			pre = pre.next;
			next = next.next;
		}
		System.out.println(next);
		return next;
	}





	private Link getLink() {
		Link link = new Link();
		for (int i = 0; i < 10; i++) {
			link.insert(new Node(i));
		}
		return link;
	}


	private class Link{
		public Node head;
		public void insert(Node node){
			if(head == null){
				head = node;
			}else{
				Node currentNode = head;
				while(currentNode.next != null){
					currentNode = currentNode.next;
				}
				currentNode.next = node;
			}
		}
		
		public String toString() {
			String display = "";
			Node currentNode = head;
			while(currentNode != null){
				display += currentNode + "--->";
				currentNode = currentNode.next;
			}
			display += "null";
			return display;
		}
	}
	
	private class Node{
		public int data;
		public Node next;
		public Node(int data){
			this.data = data;
		}
		
		@Override
		public String toString() {
			return "Node [data=" + data +"]";
		}
	}
	
}
